home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94b.txt / 000010_icon-group-sender _Fri Aug 19 10:05:22 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  4KB
  1. Received: by cheltenham.cs.arizona.edu; Fri, 19 Aug 1994 10:35:12 MST
  2. Date: Fri, 19 Aug 1994 10:05:22 +0700
  3. From: swampler@noao.edu
  4. Message-Id: <9408191705.AA24746@orpheus.gemini.edu>
  5. Subject: Re: Backtracking and reversible assigment
  6. To: icon-group@cs.arizona.edu
  7. Content-Length: 3786
  8. Errors-To: icon-group-errors@cs.arizona.edu
  9.  
  10. You wrote:
  11.  
  12. >>Can anyone explain+give a usefull example of the use of <- and complex 
  13. >>backtracking in general? (Only examples in Icon will be accepted here..)
  14. >>
  15.  
  16. Hmmm, by useful, I assume you're ruling out the 8-queens program in the
  17. Icon book (also found in the IPL)?
  18.  
  19. I don't know if I can provide much - I think that you mean 'data backtracking'
  20. when you say 'complex' backtracking (since that's what <- provides).  Most
  21. problems that are usefully attacked with data backtracking tend to be fairly
  22. complex (otherwise, it's often easy to find some other approach that's not
  23. much more difficult to use - simple problems tend to have simple solutions).
  24.  
  25. What <- gives you is the ability to 'roll-back' when backtracking decisions
  26. that were made during the 'forward-tracking' - something that's common.  It
  27. generally takes thinking in terms of backtracking to see where it's really
  28. useful.
  29.  
  30. Here's an example (in Icon!) of a course scheduling algorithm originally
  31. written by Dan Higdon at the Univ. of Texas, and slightly modified by me
  32. to handle courses at my 'old' school.  As it uses recursion, control backtracking,
  33. and data backtracking, I'd have to say it probably qualifies as 'complex', and
  34. it's definitely been found to be useful!
  35.  
  36. (I'm also a bit reluctant to post this as an isolated piece of code - it's
  37. part of a much larger program that allows students to experiment with
  38. schedules, so there are parts here that take quite a bit of context...
  39. The procedure generates successive schedules (it can indeed, produce all
  40. possible schedules from a set of courses, if you keep resuming it...))
  41.  
  42. Anyway (warning - non-trivial code follows - on the other hand, try
  43.   coding this up in C!):
  44.  
  45. #
  46. # The algorithm is as follows:
  47. # If the course set is empty, return that empty set
  48. # otherwise,
  49. #    Generate every remaining schedule and do the following with each:
  50. #       get the course name and remove it from the course set
  51. #       Generate every non-null and unconflicting time for each class, as
  52. #          well as any possible unconflicting labs for that class, then:
  53. #          insert it (and the lab) into the set
  54. #          suspend this schedule
  55. #
  56. procedure schedule (cs)            # input is a set of desired classes
  57.    local t, schedl, class, tlab
  58.  
  59.    if *cs = 0 then return cs
  60.  
  61.    delete(cs,class := ?cs)        # pick a desired class at random
  62.  
  63.    every schedl := schedule(cs) &       # first schedule all *other* classes,
  64.                     #   then try and fit this one (and lab)
  65.          freespace(t := !classdb[class]) & nonConflicting(t, schedl) &
  66.          (/t.lab | nonConflicting(tlab <- !\t.lab,schedl))
  67.  
  68.       do {                # found room, add it (and lab) to schedule
  69.          suspend set([t, \tlab] | [t])\1 ++ schedl
  70.          }
  71. end
  72.  
  73. Control backtracking is used to 'go back and try another one' if either:
  74.  
  75.    (1) there is no room in that particular class
  76.    (2) that class conflicts with already scheduled classes
  77.    (3) that course has a required lab that can't fit into the schedule
  78.  
  79. The use here of data backtracking, in:
  80.  
  81.     tlab <- !\t.lab
  82.  
  83. is to restore the initial value of tlab (&null, since it's a local variable)
  84. if none of the available labs for this course can be fit into the schedule.
  85.  
  86. freespace() checks a class to see if there are any available seats left,
  87.  with !classdb[class] producing all sections of that class...
  88.  
  89. nonConflicting() checks to be sure the section doesn't overlap with an already
  90. scheduled class.
  91.  
  92. The /t.lab | nonConflicting(...) avoids calling nonConflicting is there is
  93. no lab for that course, without failing.
  94.  
  95. The
  96.  
  97.     set([t, \tlab] | [t])\1 ++ schedl
  98.  
  99. adds either a pair (if there was a lab), or a single (if not) to the
  100. schedule.  The limitation prevents backtracking from generating
  101. both!
  102.  
  103.  
  104. --
  105. Steve Wampler
  106. swampler@gemini.edu
  107. Gemini Project (under AURA)
  108.